<!DOCTYPE HTML>
<html lang="zh-Hans" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>简单写个Rust无锁队列 - Rust 优秀博文</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="../../favicon.svg">
        <link rel="shortcut icon" href="../../favicon.png">
        <link rel="stylesheet" href="../../css/variables.css">
        <link rel="stylesheet" href="../../css/general.css">
        <link rel="stylesheet" href="../../css/chrome.css">
        <link rel="stylesheet" href="../../css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="../../fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="../../highlight.css">
        <link rel="stylesheet" href="../../tomorrow-night.css">
        <link rel="stylesheet" href="../../ayu-highlight.css">

        <!-- Custom theme stylesheets -->

    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "../../";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">1.</strong> 类型系统</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../01_类型系统/Rust_Concept_Clarification_Deref_vs_AsRef_vs_Borrow_vs_Cow/Rust_Concept_Clarification_Deref_vs_AsRef_vs_Borrow_vs_Cow.html"><strong aria-hidden="true">1.1.</strong> Rust Concept Clarification Deref vs AsRef vs Borrow vs Cow</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust_Concept_Clarification_Deref_vs_AsRef_vs_Borrow_vs_Cow/Deref_AsRef_Borrow_Cow释义.html"><strong aria-hidden="true">1.2.</strong> Deref AsRef Borrow Cow 释义</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust的Borrow和AsRef：让你的代码用起来像呼吸一样自然/Rust的Borrow和AsRef：让你的代码用起来像呼吸一样自然.html"><strong aria-hidden="true">1.3.</strong> Rust的Borrow和AsRef：让你的代码用起来像呼吸一样自然</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust的Cow类型有什么用？详解Cow及其用途/Rust的Cow类型有什么用？详解Cow及其用途.html"><strong aria-hidden="true">1.4.</strong> Rust的Cow类型有什么用？详解Cow及其用途</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/判别Fn、FnMut、FnOnce的标准/判别Fn、FnMut、FnOnce的标准.html"><strong aria-hidden="true">1.5.</strong> 判别Fn、FnMut、FnOnce的标准</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/一行代码告诉你内部可变性的真相(UnsafeCell)/一行代码告诉你内部可变性的真相(UnsafeCell).html"><strong aria-hidden="true">1.6.</strong> 一行代码告诉你内部可变性的真相(UnsafeCell)</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Tour_of_Rust's_Standard_Library_Traits/Tour_of_Rust's_Standard_Library_Traits.html"><strong aria-hidden="true">1.7.</strong> Tour of Rust's Standard Library Traits</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/逆变、协变与子类型，以及Rust/逆变、协变与子类型，以及Rust.html"><strong aria-hidden="true">1.8.</strong> 逆变、协变与子类型，以及Rust</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust自引用结构、Pin与Unpin/Rust自引用结构、Pin与Unpin.html"><strong aria-hidden="true">1.9.</strong> Rust自引用结构、Pin与Unpin</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/为什么Rust需要Pin,Unpin/为什么Rust需要Pin,Unpin.html"><strong aria-hidden="true">1.10.</strong> 译：为什么 Rust 需要 Pin, Unpin ？</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/定海神针Pin和Unpin/定海神针Pin和Unpin.html"><strong aria-hidden="true">1.11.</strong> 译：定海神针 Pin 和 Unpin</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/sizedness-in-rust/sizedness-in-rust.html"><strong aria-hidden="true">1.12.</strong> Sizedness in Rust</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust生命周期集大成者PhantomData〈T〉/Rust生命周期集大成者PhantomData〈T〉.html"><strong aria-hidden="true">1.13.</strong> Rust生命周期集大成者 PhantomData&lt;T&gt;</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用Rust做类型体操_Part_0.html"><strong aria-hidden="true">1.14.</strong> 数据库表达式执行的黑魔法：用Rust做类型体操 Part 0</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：GAT实现引用类型关联_Part_1.html"><strong aria-hidden="true">1.15.</strong> 数据库表达式执行的黑魔法：GAT实现引用类型关联 Part 1</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用HRTB写bound_Part_2.html"><strong aria-hidden="true">1.16.</strong> 数据库表达式执行的黑魔法：用HRTB写bound Part 2</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用Rust做类型体操之用宏展开重复代码_Part_3_&_4.html"><strong aria-hidden="true">1.17.</strong> 数据库表达式执行的黑魔法：用Rust做类型体操之用宏展开重复代码 Part 3 & 4</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：与Rust编译器斗智斗勇之表达式向量化_Part_5_&_6.html"><strong aria-hidden="true">1.18.</strong> 数据库表达式执行的黑魔法：与Rust编译器斗智斗勇之表达式向量化 Part 5 & 6</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：在Rust中用宏关联逻辑类型和实际类型_Part_7.html"><strong aria-hidden="true">1.19.</strong> 数据库表达式执行的黑魔法：在Rust中用宏关联逻辑类型和实际类型 Part 7</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">2.</strong> 生命周期</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../02_生命周期/Rust中的生命周期——从StrSplit实例说开去/Rust中的生命周期——从StrSplit实例说开去.html"><strong aria-hidden="true">2.1.</strong> Rust中的生命周期——从StrSplit实例说开去</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/与ChatGPT深度对话来学Rust生命周期/与ChatGPT深度对话来学Rust生命周期.html"><strong aria-hidden="true">2.2.</strong> 与ChatGPT深度对话来学Rust生命周期</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——early_bound与late_bound（1）/进击的Rust生命周期——early_bound与late_bound（1）.html"><strong aria-hidden="true">2.3.</strong> 进击的Rust生命周期——early_bound与late_bound（1）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——early_bound与late_bound（2）/进击的Rust生命周期——early_bound与late_bound（2）.html"><strong aria-hidden="true">2.4.</strong> 进击的Rust生命周期——early_bound与late_bound（2）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——一力降十会的MIR（1）/进击的Rust生命周期——一力降十会的MIR（1）.html"><strong aria-hidden="true">2.5.</strong> 进击的Rust生命周期——一力降十会的MIR（1）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——一力降十会的MIR（2）/进击的Rust生命周期——一力降十会的MIR（2）.html"><strong aria-hidden="true">2.6.</strong> 进击的Rust生命周期——一力降十会的MIR（2）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/Common_Rust_Lifetime_Misconceptions/Common_Rust_Lifetime_Misconceptions.html"><strong aria-hidden="true">2.7.</strong> Common Rust Lifetime Misconceptions</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/Rust生命周期常见误区/Rust生命周期常见误区.html"><strong aria-hidden="true">2.8.</strong> 译：Rust生命周期常见误区</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">3.</strong> 无畏并发</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../05_无畏并发/简单写个Rust无锁队列/简单写个Rust无锁队列.html" class="active"><strong aria-hidden="true">3.1.</strong> 简单写个Rust无锁队列</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/进击的Rust多线程——混合自旋锁/进击的Rust多线程——混合自旋锁.html"><strong aria-hidden="true">3.2.</strong> 进击的Rust多线程——混合自旋锁</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/An_unsafe_tour_of_Rust's_Send_and_Sync/An_unsafe_tour_of_Rust's_Send_and_Sync.html"><strong aria-hidden="true">3.3.</strong> An unsafe tour of Rust's Send and Sync</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/进击的Rust多线程——Send与Sync/进击的Rust多线程——Send与Sync.html"><strong aria-hidden="true">3.4.</strong> 进击的Rust多线程——Send与Sync</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/进击的Rust多线程——离经叛道的PhantomData/进击的Rust多线程——离经叛道的PhantomData.html"><strong aria-hidden="true">3.5.</strong> 进击的Rust多线程——离经叛道的PhantomData</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/Rust_Async_Pin概念解析/Rust_Async_Pin概念解析.html"><strong aria-hidden="true">3.6.</strong> Rust Async: Pin概念解析</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/Rust和C++的并发库对比/Rust和C++的并发库对比.html"><strong aria-hidden="true">3.7.</strong> 译：Rust 和 C++ 的并发库对比</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/Rust原子类型和内存排序/Rust原子类型和内存排序.html"><strong aria-hidden="true">3.8.</strong> Rust原子类型和内存排序</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">4.</strong> 网络编程</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../06_网络编程/从编解码层面理解WebSocket_手写一个WebSocket/从编解码层面理解WebSocket_手写一个WebSocket.html"><strong aria-hidden="true">4.1.</strong> 从编解码层面理解WebSocket 手写一 个WebSocket</a></li><li class="chapter-item expanded "><a href="../../06_网络编程/透过Rust探索系统的本原：网络篇/透过Rust探索系统的本原：网络篇.html"><strong aria-hidden="true">4.2.</strong> 透过Rust探索系统的本原：网络篇</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">5.</strong> 轮子系列</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../07_轮子系列/700行Rust写一个内存分配器/700行Rust写一个内存分配器.html"><strong aria-hidden="true">5.1.</strong> 700行Rust写一个内存分配器</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/Rust：网络库的实现思路/Rust：网络库的实现思路.html"><strong aria-hidden="true">5.2.</strong> Rust：网络库的实现思路</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/Rust异步运行时基础部件/Rust异步运行时基础部件.html"><strong aria-hidden="true">5.3.</strong> Rust异步运行时基础部件</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/使用Rust+epoll编写异步IO框架/使用Rust+epoll编写异步IO框架（1）.html"><strong aria-hidden="true">5.4.</strong> 使用Rust+epoll编写异步IO框架（1）</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/使用Rust+epoll编写异步IO框架/使用Rust+epoll编写异步IO框架（2）.html"><strong aria-hidden="true">5.5.</strong> 使用Rust+epoll编写异步IO框架（2）</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/使用Rust+epoll编写异步IO框架/使用Rust+epoll编写异步IO框架（3）.html"><strong aria-hidden="true">5.6.</strong> 使用Rust+epoll编写异步IO框架（3）</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day1.html"><strong aria-hidden="true">5.7.</strong> 用rust从零开发一套web框架：day1</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day2.html"><strong aria-hidden="true">5.8.</strong> 用rust从零开发一套web框架：day2</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day3.html"><strong aria-hidden="true">5.9.</strong> 用rust从零开发一套web框架：day3</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day4.html"><strong aria-hidden="true">5.10.</strong> 用rust从零开发一套web框架：day4</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day5.html"><strong aria-hidden="true">5.11.</strong> 用rust从零开发一套web框架：day5</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">6.</strong> 奇技淫巧</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../08_奇技淫巧/Copy-On-Write是不是优化？/Copy-On-Write是不是优化？.html"><strong aria-hidden="true">6.1.</strong> 译：Copy-On-Write是不是优化？</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/揭秘神奇的Rust_Axum风格的函数实现/揭秘神奇的Rust_Axum风格的函数实现.html"><strong aria-hidden="true">6.2.</strong> 译：揭秘神奇的 Rust Axum 风格的函数实现</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/“变长参数”函数与回调/“变长参数”函数与回调.html"><strong aria-hidden="true">6.3.</strong> “变长参数”函数与回调</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/Rust字符串格式化的幕后：format_args!()/Rust字符串格式化的幕后：format_args!().html"><strong aria-hidden="true">6.4.</strong> 译：Rust字符串格式化的幕后：format_args!()</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/给Rust带来一点C++特产/给Rust带来一点C++特产.html"><strong aria-hidden="true">6.5.</strong> 给Rust带来一点C++特产</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/一步步实现_Rust_Bevy_ECS_的_System_简化版本/一步步实现_Rust_Bevy_ECS_的_System_简化版本.html"><strong aria-hidden="true">6.6.</strong> 一步步实现 Rust Bevy ECS 的 System 简化版本</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/Exploring_Design_Patterns_in_Rust_with_Algorithmic_Trading_Examples/Exploring_Design_Patterns_in_Rust_with_Algorithmic_Trading_Examples.html"><strong aria-hidden="true">6.7.</strong> Exploring Design Patterns in Rust with Algorithmic Trading Examples</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">7.</strong> 源码分析</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../09_源码分析/Rust并发：bytes源码分析/Rust并发：bytes源码分析.html"><strong aria-hidden="true">7.1.</strong> Rust并发：bytes源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust并发：标准库Arc源码分析/Rust并发：标准库Arc源码分析.html"><strong aria-hidden="true">7.2.</strong> Rust并发：标准库Arc源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust并发：标准库sync_Once源码分析/Rust并发：标准库sync_Once源码分析.html"><strong aria-hidden="true">7.3.</strong> Rust并发：标准库sync::Once源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust源码阅读：引用计数Rc/Rust源码阅读：引用计数Rc.html"><strong aria-hidden="true">7.4.</strong> Rust源码阅读：引用计数Rc</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust源码阅读：Cell、RefCell与内部可变性/Rust源码阅读：Cell、RefCell与内部可变性.html"><strong aria-hidden="true">7.5.</strong> Rust源码阅读： Cell、RefCell与内部可变性</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/关于_Rust_的_UnsafeCell、Cell_与_RefCell/关于_Rust_的_UnsafeCell、Cell_与_RefCell.html"><strong aria-hidden="true">7.6.</strong> 关于 Rust 的 UnsafeCell、Cell 与 RefCell</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust_Async_async-stream源码分析/Rust_Async_async-stream源码分析.html"><strong aria-hidden="true">7.7.</strong> Rust Async: async-stream源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/走进Tokio的异步世界/走进Tokio的异步世界.html"><strong aria-hidden="true">7.8.</strong> 走进 Tokio 的异步世界</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/tokio.rs_runtime的实现/tokio.rs_runtime的实现.html"><strong aria-hidden="true">7.9.</strong> tokio.rs runtime 的实现</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Tokio_internals/Tokio_internals.html"><strong aria-hidden="true">7.10.</strong> Tokio internals</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Tokio_internals/译文：Tokio內部机制.html"><strong aria-hidden="true">7.11.</strong> 译：Tokio 内部机制</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust_Axum_HTTP_框架的架构分析/Rust_Axum_HTTP_框架的架构分析.html"><strong aria-hidden="true">7.12.</strong> Rust Axum HTTP 框架的架构分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/安利一个Rust_Game_Engine：Bevy--ECS部分/安利一个Rust_Game_Engine：Bevy--ECS部分.html"><strong aria-hidden="true">7.13.</strong> 安利一个Rust Game Engine：Bevy--ECS部分</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Tokio_解析之任务调度/Tokio_解析之任务调度.html"><strong aria-hidden="true">7.14.</strong> Tokio 解析之任务调度</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">8.</strong> 生态观察</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../11_生态观察/Rust_web_frameworks_have_subpar_error_reporting/Rust_web_frameworks_have_subpar_error_reporting.html"><strong aria-hidden="true">8.1.</strong> Rust web frameworks have subpar error reporting</a></li><li class="chapter-item expanded "><a href="../../11_生态观察/SeaORM：要做Rust版本的ActiveRecord/SeaORM：要做Rust版本的ActiveRecord.html"><strong aria-hidden="true">8.2.</strong> SeaORM：要做Rust版本的ActiveRecord</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">9.</strong> 死灵终极</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_总述.html"><strong aria-hidden="true">9.1.</strong> 译：Learn Rust the Dangerous Way 总述</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_0.html"><strong aria-hidden="true">9.2.</strong> 译：Learn Rust the Dangerous Way 0</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_1.html"><strong aria-hidden="true">9.3.</strong> 译：Learn Rust the Dangerous Way 1</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_2.html"><strong aria-hidden="true">9.4.</strong> 译：Learn Rust the Dangerous Way 2</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_3.html"><strong aria-hidden="true">9.5.</strong> 译：Learn Rust the Dangerous Way 3</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_4.html"><strong aria-hidden="true">9.6.</strong> 译：Learn Rust the Dangerous Way 4</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_5.html"><strong aria-hidden="true">9.7.</strong> 译：Learn Rust the Dangerous Way 5</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测（一）.html"><strong aria-hidden="true">9.8.</strong> Unsafe Rust 随堂小测（一）</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测（二）.html"><strong aria-hidden="true">9.9.</strong> Unsafe Rust 随堂小测（二）</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测（三）.html"><strong aria-hidden="true">9.10.</strong> Unsafe Rust 随堂小测（三）</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测参考答案.html"><strong aria-hidden="true">9.11.</strong> Unsafe Rust 随堂小测参考答案</a></li></ol></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">Rust 优秀博文</h1>

                    <div class="right-buttons">
                        <a href="../../print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="简单写个rust无锁队列"><a class="header" href="#简单写个rust无锁队列">简单写个Rust无锁队列</a></h1>
<p>作者：<a href="https://www.zhihu.com/people/qing-qing-zi-jin-77-54">荣富强-BI1RFQ</a></p>
<p>原载：<a href="https://zhuanlan.zhihu.com/p/527500869">https://zhuanlan.zhihu.com/p/527500869</a></p>
<p>感谢 <a href="https://www.zhihu.com/people/104a5047e3e4a219fb1aa195ec3f8917">@LuXts</a> 在评论区的勘误，入队算法伪代码有误，已经更正。</p>
<p>鄙人博客原文地址：</p>
<p><a href="https://link.zhihu.com/?target=https%3A//clslaid.icu/implement-lockless-unsafe-queue/">https://clslaid.icu/implement-lockless-unsafe-queue/clslaid.icu/implement-lockless-unsafe-queue/</a></p>
<p>仓库源代码地址（请勿用于生产环境，后果自负）：</p>
<p><a href="https://link.zhihu.com/?target=https%3A//github.com/clslaid/l3queue.git">l3queuegithub.com/clslaid/l3queue.git</a></p>
<p>在写毕设的时候总会在 crates.io、docs.io 等网站转悠，查询有没有高性能的缓存实现可以稍微拉高一点毕设性能。而在琳琅满目的第三方缓存库中，总有一些库打出“无锁”的招牌，好像用到了无锁并发编程技术性能就有质的飞跃一般。不过一直没有亲自去学习应用这些技术到自己写的数据结构中——毕竟套个 Mutex，讲究一点套个 RwLock，也就20秒的事。😏</p>
<p>而最近面试某司时，面试官出了一个使用 Rust 写无锁链表队列的面试题。其实说到底也就一个链表罢，俺这么想着，便打开了面试官发来的论文<sup class="footnote-reference"><a href="#lockless">1</a></sup>开始阅读。</p>
<div class="footnote-definition" id="lockless"><sup class="footnote-definition-label">1</sup>
<p>J. D. Valois, ‘Implementing Lock-Free Queues’, <em>In Proceedings of the Seventh International Conference on Parallel and Distributed Computing Systems, Las Vegas</em>, NV, 1994. pp.64–69.</p>
</div>
<h2 id="什么是无锁"><a class="header" href="#什么是无锁">什么是无锁</a></h2>
<p><img src="pict/v2-e36d3a73e8159dba999282d0c467a58d_1440w.png" alt="" /></p>
<p>“无锁”与“有锁”相对，指的是不适用互斥锁，而是基于 CPU 提供的 <a href="https://zh.m.wikipedia.org/zh-hans/%E6%AF%94%E8%BE%83%E5%B9%B6%E4%BA%A4%E6%8D%A2">Compare and Swap</a>、<a href="https://zh.m.wikipedia.org/zh-hans/Fetch-and-add">Fetch and Add</a> 等原子操作，直接实现并发数据结构的方法。有锁数据结构的主要缺点有：</p>
<ul>
<li>阻塞：
若获得锁的线程被挂起，那么其他线程也只能阻塞等待</li>
<li>优先级反转：
若低优先级的线程已经持有某临界资源上的锁，在高优先级线程抢占并请求该临界资源上的锁时，会导致“空转”</li>
<li>不适用所有场合：
用于<a href="https://man7.org/linux/man-pages/man7/signal.7.html">信号</a>处理函数和中断时容易出现死锁问题</li>
</ul>
<p>而无锁数据结构克服了上述问题，在无锁数据结构上的操作是不互斥的，由此便克服了阻塞和优先级反转问题；同时也使得信号处理函数和中断处理可以直接在数据结构上进行操作而不用担心锁已经被其他线程获取，不会发生死锁。总而言之，<strong>无锁数据结构上的操作不会因为某个参与并行的线程被挂起，而影响其他所有线程的正常工作</strong>。</p>
<p>但是通常情况下实现有锁数据结构比无锁数据结构简单得多。</p>
<h3 id="原子操作简介"><a class="header" href="#原子操作简介">原子操作简介</a></h3>
<p>原子操作满足原子性，简单来说是指该操作一气呵成<strong>不可再分</strong>，要么做了，要么没做。同时原子操作一旦被执行就只能一直执行到完成，期间<strong>无法被调度器所干扰</strong>。</p>
<h4 id="compare-and-swap"><a class="header" href="#compare-and-swap">Compare and Swap</a></h4>
<p>比较与交换是一种原子操作，基本思想是将数据现在的状态与给定状态进行比较。若现在的状态与给定状态一致，那么就将数据的状态修改为目标状态并返回真；否则则不修改数据并返回假。</p>
<p>C++ 伪代码如下：</p>
<pre><code class="language-C++">bool CAS(T &amp;data, T current, T target) {
    if (data == current) {
        data = target;
        return true;
    }
    return false;
}
</code></pre>
<h4 id="指令重排与内存顺序"><a class="header" href="#指令重排与内存顺序">指令重排与内存顺序</a></h4>
<p>为了优化程序的性能，编译器和 CPU 通常会将编译出来的二进制代码进行指令重排和乱序执行，导致程序二进制码、硬件执行和源码操作顺序实际上并不一致。内存顺序标记可以用于限制编译器和 CPU 进行过度优化导致程序的语义出现问题。</p>
<p>在 Rust 中有 5 种内存顺序标记，分别是 <code>Relaxed</code>、<code>Acquire</code>、<code>Release</code>、<code>AcqRel</code> 和 <code>SeqCst</code>。它们的语义和 C++20 标准中一致。一般来说，完全不限制优化可以用 <code>Relaxed</code>，读操作用 <code>Acquire</code>，写操作用 <code>Release</code>，读+写用 <code>AcqRel</code>，不清楚用甚么就用最为严格的 <code>SeqCst</code>。详情可以阅读<a href="https://rustmagazine.github.io/rust_magazine_2022/Q1/contribute/atom.html">Rust原子类型与内存排序</a>和<a href="https://doc.rust-lang.org/std/sync/atomic/enum.Ordering.html">std::sync::atomic::Ordering</a>。</p>
<h2 id="无锁队列算法"><a class="header" href="#无锁队列算法">无锁队列算法</a></h2>
<p>论文<sup class="footnote-reference"><a href="#lockless">1</a></sup>中描述的链表队列是基于空链表的。相比于非空链表实现，空链表对链表为空的情形的处理更加简单。</p>
<h3 id="内存布局"><a class="header" href="#内存布局">内存布局</a></h3>
<p><img src="pict/v2-d8a1194dd00f37348764dcf27cf9e911_1440w.webp" alt="" /></p>
<p>整个链表的内存布局如图所示，看起来平平无奇。链表为一个单链表，链表队列的 <code>Head</code> 指针指向头结点，<code>Tail</code> 指向下游的尾节点。出队时，<code>Head</code> 指针会向后移动一步，并将新指向的节点承载的数据返回。如果<code>Head</code>指向的节点为尾节点，那就说明当前这个队列为空，直接返回空值。当进行入队操作时，新的数据节点会被塞入链表尾部，并更新 <code>Tail</code> 使之指向新尾部。</p>
<p>但要实现安全的并发，需要依靠原子操作来实现出队和入队算法。</p>
<h3 id="入队算法"><a class="header" href="#入队算法">入队算法</a></h3>
<p>入队算法主要分三个阶段，第一个阶段在堆上构造出承载新数据的节点，第二个阶段寻找链表尾并将节点插入链表，最后一个阶段更新 tail 指针指向真正的链表尾部。</p>
<p>入队算法有两种。主要区别在于 tail 指针的严格程度。第一种对 tail 的要求比较严格，可以保证 tail 指针始终指向真正的整个链表的尾部。算法的 C++ 伪代码如下：</p>
<pre><code class="language-C++">void enqueue(T x) {
    // 阶段 1
    // 在堆上构建新节点
    Node&lt;T&gt; *q = new Node&lt;T&gt;;
    q -&gt; value = x;
    q -&gt; next = nullptr;

    // 阶段2
    bool succ;
    Node&lt;T&gt; *p;
    do {
        // 尝试插入链表尾部
        p = tail;
        succ = CAS(p-&gt;next, nullptr, q);
        if !succ {
            // 插入失败，可能有另一个线程也在插入
            // 尝试更新 tail 指针一步，失败了没有关系
            CAS(tail, p, p-&gt;next);
            // 可以防止另一个已经完成二阶段的线程
            // 在快执行第三阶段时挂起
            // 导致本线程死循环
        }
    } while(!succ)
    // 阶段3
    // 更新 tail 指针指向本线程插入的尾部
    CAS(tail, p, q);
    // 失败了说明 tail 已经不指向 p 了
    // 可能是因为另一个线程执行了第二阶段的更新 tail 操作
    // 此时 tail == q
    // 真正的链表尾部也可能也已经不是 q
}
</code></pre>
<p>而另一种算法则视 tail 指针为一种对链表尾部的提示，并不保证指向链表尾部。此时就需要程序自己从 tail 开始遍历链表找到真正的链表尾部。</p>
<p>C++ 伪代码如下：</p>
<pre><code class="language-C++">void enqueue(T x) {
    // 阶段1
    // 构建堆上的新节点
    Node&lt;T&gt;* q = new Node&lt;T&gt;;
    q -&gt; value = x;
    q -&gt; next = nullptr;
    
    // 阶段2
    // 尝试将节点插入链表尾部
    auto p = tail;
    auto old_p = p;
    do {
        while (nullptr != p -&gt; next) {
            // 遍历到真正的链表尾部
            p = p -&gt; next;
        }
        // CAS 成功时说明抵达了真正的链表尾部
    } while(!CAS(p-&gt;next, nullptr, q))

    // 阶段3
    // 更新 tail 到本线程插入的链表尾部
    CAS(tail, old_p, q);
}
</code></pre>
<p>最后的实现中经过测试其实两个算法的复杂度和带宽都是相近的。事实上，第一种算法可以看作第二种算法的“厚道”版本，在遍历时同时捎带上了 tail 指针。</p>
<p>本文选择实现第二种算法。</p>
<h3 id="出队算法"><a class="header" href="#出队算法">出队算法</a></h3>
<p>出队算法相比更加简单，第一个阶段将 head 指针从头结点向后移动一步，第二个阶段则获取头节点的邻接节点上的数据并返回。真嘅好 simple 啊！伪代码如下：</p>
<pre><code class="language-C++">std::optional&lt;T&gt; dequeue() {
    // 阶段1
    Node&lt;T&gt; *p;
    do {
        // 获取头结点
        p = head;
        if (nullptr == p -&gt; next) {
            // 链表已经是空的，那就返回个空罢
            return {};
        }
        // 尝试将 head 向后移动一步
        // 失败则说明手上的 p 已经过时了，再来一次
    } while(!CAS(head, p, p-&gt;next))
    // 阶段2
    // 返回数据
    return p -&gt; next -&gt; value;
}
</code></pre>
<p>不过，稍有C/C++经验的人都能看出：“你怎么不 free/delete 呢？如果一个一个一个dequeue出来的都不回收，内存会泄露罢！”是的，不过笔者当时觉得到时候加上即可，后面证明这里隐藏着天大的麻烦...</p>
<h2 id="需求"><a class="header" href="#需求">需求</a></h2>
<p>别忘了这是一个面试题，面试官需要：</p>
<ol start="0">
<li>用 rust 实现该数据结构</li>
<li>数据结构应当实现以上的出队和入队算法</li>
<li>测试、对比最终实现与<code>std::collections::LinkedList</code>上套<code>Mutex</code>的性能。</li>
<li>编写报告</li>
</ol>
<h2 id="设计与实现"><a class="header" href="#设计与实现">设计与实现</a></h2>
<p>每个 Rust 用户都会有这样的经历：</p>
<ol>
<li>到达内存安全新境界——Rust！</li>
<li>太高级了 Rust！</li>
<li>诶呀这不链表吗？</li>
<li>还是看看远处的 <code>unsafe</code> 吧家人们...</li>
</ol>
<p>其实单链表还能使用 <code>Box</code> 等智能指针解决问题，一行 unsafe 都不用写，你大可以~~像相信先锋级泰坦一样~~相信 rustc。</p>
<p>不过还是先看看手头上有什么吧！</p>
<h3 id="rust-原子类型与原子操作"><a class="header" href="#rust-原子类型与原子操作">Rust 原子类型与原子操作</a></h3>
<p>Rust 标准库内置了基本的原子类型如 <code>AtomicBool</code>、<code>AtomicUsize</code>、<code>AtomicPtr</code> 等。原子类型都支持 <code>load</code>、<code>store</code> 等方法访问内部值，也都支持 FAA、CAS 等原子操作。同时这些原子类型提供了内部可变性，不需要获取其可变引用就可以通过调用 <code>store</code>、<code>compare_exchange</code> 等方法改变内部的值。</p>
<p>悲催的是，Rust的智能指针并不支持原子操作，于是无法使用 <code>Option&lt;Arc&lt;Node&lt;T&gt;&gt;&gt;</code> 或者 <code>Arc&lt;Node&lt;T&gt;&gt;</code>。而 <code>AtomicPtr</code> 充其量只是一个支持原子操作的裸指针—— <code>unsafe</code> 不可避（悲）。</p>
<h3 id="数据节点"><a class="header" href="#数据节点">数据节点</a></h3>
<p>不妨令承载的数据类型为 T，则节点的类型为 <code>Node&lt;T&gt;</code>。</p>
<p>T 类型数据可能构造起来非常的麻烦，因此我们的数据项使用 <code>Option&lt;T&gt;</code>，如此我们在构建最初的头节点直接用 <code>Option::None</code> 即可。</p>
<p>为了支持原子操作，节点之间的指针只能使用 <code>AtomicPtr&lt;Node&lt;T&gt;&gt;</code>。由此定义数据节点及其工厂函数：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>type NodePtr&lt;T&gt; = AtomicPtr&lt;Node&lt;T&gt;&gt;;

struct Node&lt;T&gt; {
    pub item: Option&lt;T&gt;,
    pub next: NodePtr&lt;T&gt;,
}

impl&lt;T&gt; Node&lt;T&gt; {
    pub fn new(x: T) -&gt; Self {
        Self {
            item: Some(x),
            next: AtomicPtr::from(std::ptr::null_mut()),
        }
    }
    pub fn new_empty() -&gt; Self {
        Self {
            item: None,
            next: AtomicPtr::from(std::ptr::null_mut()),
        }
    }
}
<span class="boring">}
</span></code></pre></pre>
<h3 id="链表队列"><a class="header" href="#链表队列">链表队列</a></h3>
<p>队列结构体应当包含 head、tail 两个指针。由于前述原因它们的类型也只能是 <code>NodePtr&lt;T&gt;</code> (即 <code>AtomicPtr&lt;Node&lt;T&gt;&gt;</code>)。</p>
<p>链表队列作为一个容器最好还是能有一个 O(1) 复杂度的方法可以知道它的长度，因此给它添加一个记录长度的 <code>AtomicUsize</code>。
可以给出定义和求容量的代码如下：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub struct LinkedQueue&lt;T&gt; {
    len: AtomicUsize,
    head: NodePtr&lt;T&gt;,
    tail: NodePtr&lt;T&gt;,
}

impl&lt;T&gt; LinkedQueue&lt;T&gt; {
    pub fn size(&amp;self) -&gt; usize{
        self.len.load(Ordering::SeqCst);
    }
    pub fn is_empty(&amp;self) -&gt; usize {
        0 == self.len.load(Ordering::SeqCst);
        // 当然，更准确的方法应该是
        // 检查 self.head -&gt; next 是不是空的
    }
}
<span class="boring">}
</span></code></pre></pre>
<p>由于链表为空链表，因此在链表创建时就应当创建一个堆上的节点。可以通过 <code>Box::new(x)</code> 创建一个指向堆上数据的 <code>Box</code> 指针，然后通过调用 <code>Box::leak(Self)</code> 或 <code>Box::into_raw(Self)</code> 函数即可将 <code>Box</code> 指针转为可变引用(&amp;mut T)或者裸可变指针(*mut T)。此时堆上数据就归你自己管辖了！</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub fn new() -&gt; Self {
    let empty_node = Box::new(Node&lt;T&gt;::new_empty());
    let node_ptr = Box::into_raw(empty_node);
    let head = AtomicPtr::from(node_ptr);
    let tail = AtomicPtr::from(node_ptr);
    Self {
        len: AtomicUsize::new(0),
        head,
        tail
    }
}
<span class="boring">}
</span></code></pre></pre>
<p>注意万万不可使用 <code>Box::as_mut(&amp;self)</code> 等方法获得地址，使用该方法并不会消耗 <code>Box</code>——堆上内存的生存期还限制在当前函数内部，一旦离开其作用域就会释放！——入队的时候就会吃到一发 <code>SIGSEG</code>。</p>
<h3 id="内存布局-1"><a class="header" href="#内存布局-1">内存布局</a></h3>
<p>数据结构的内存布局应当如下：</p>
<pre><code class="language-txt">插入：1、1、4、5、1、4
                     ┌─────────────┐
                  ┌─►│Node&lt;T&gt;      │
                  │  ├─────────────┤
                  │  │ item        │
                  │  │ None        │
┌───────────────┐ │  ├─────────────┤
│LinkedQueue&lt;T&gt; │ │  │ next        ├──┐
├───────────────┤ │  │ NodePtr&lt;T&gt;  │  │
│ len           │ │  └─────────────┘  │
│ AtomicUsize   │ │                   │
├───────────────┤ │  ┌─────────────┐  │   ┌─────────────┐     ┌─────────────┐
│ head          ├─┘  │Node&lt;T&gt;      │◄─┘ ┌►│Node&lt;T&gt;      │   ┌►│Node&lt;T&gt;      │
│ NodePtr&lt;T&gt;    │    ├─────────────┤    │ ├─────────────┤   │ ├─────────────┤
├───────────────┤    │ item        │    │ │ item        │   │ │ item        │
│ tail          ├─┐  │ Some(1)     │    │ │ Some(1)     │   │ │ Some(4)     │
│ NodePtr&lt;T&gt;    │ │  ├─────────────┤    │ ├─────────────┤   │ ├─────────────┤
└───────────────┘ │  │ next        ├────┘ │ next        ├───┘ │ next        ├───┐
                  │  │ NodePtr&lt;T&gt;  │      │ NodePtr&lt;T&gt;  │     │ NodePtr&lt;T&gt;  │   │
                  │  └─────────────┘      └─────────────┘     └─────────────┘   │
                  │                                                             │
                  │  ┌─────────────┐      ┌─────────────┐     ┌─────────────┐   │
                  └─►│Node&lt;T&gt;      │◄┐    │Node&lt;T&gt;      │◄┐   │Node&lt;T&gt;      │◄──┘
                     ├─────────────┤ │    ├─────────────┤ │   ├─────────────┤
                     │ item        │ │    │ item        │ │   │ item        │
                     │ Some(4)     │ │    │ Some(1)     │ │   │ Some(5)     │
                     ├─────────────┤ │    ├─────────────┤ │   ├─────────────┤
       nullptr ◄─────┤ next        │ └────┤ next        │ └───┤ next        │
                     │ NodePtr&lt;T&gt;  │      │ NodePtr&lt;T&gt;  │     │ NodePtr&lt;T&gt;  │
                     └─────────────┘      └─────────────┘     └─────────────┘
</code></pre>
<h3 id="入队算法-1"><a class="header" href="#入队算法-1">入队算法</a></h3>
<p>方法签名：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub fn push(&amp;self, item: T);
<span class="boring">}
</span></code></pre></pre>
<p>本文实现前述第二种入队算法，首先在堆上创建要插入数据的节点。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>let new_node = Box::new(Node::new(item));
let node_ptr: *mut Node&lt;T&gt; = Box::into_raw(new_node);
<span class="boring">}
</span></code></pre></pre>
<p>Rust 中的原子类型只支持通过调用 <code>load(&amp;self, ordering)</code> 获取值，而解引用裸指针属于 unsafe 操作。为了代码的美观性将入队算法的循环使用一整个 unsafe 块括了起来。好吧，下水！</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>// 注意作用域，unsafe 里的东西出不来
let old_tail: *mut Node&lt;T&gt; = self.tail.load(Ordering::Acquire);
unsafe {
    // 拿到尾节点的 next 域，这是个 unsafe 操作
    let mut tail_next: &amp;NodePtr&lt;T&gt; = &amp;(*old_tail).next;
    // 循环尝试修改尾节点的 next 域
    while tail_next
        .compare_exchange(
            ptr::null_mut(),
            node_ptr,   // 欲插入的节点
            Ordering::Release,
            Ordering::Relaxed,
        )
        .is_err()
    {
        // 修改失败了，说明 tail_next 并不是真正尾节点的 next 域
        // 那就从那个冒牌货的下一个节点开始找真正的尾节点吧！
        let mut tail = tail_next.load(Ordering::Acquire);

        // 开始遍历
        loop {
            let nxt = (*tail).next.load(Ordering::Acquire);
            if nxt.is_null() {
                // 噫！中咧！
                break;
            }
            // 不要停下来啊（指找尾节点）
            tail = nxt;
        }

        // 诶哈哈，尾节点的 next 来咯！
        tail_next = &amp;(*tail).next;
    }
}
<span class="boring">}
</span></code></pre></pre>
<p>最后还是要更新一个！</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>let _ = self.tail.compare_exchange(old_tail, node_ptr, Ordering::Release, Ordering::Relaxed);
// +1size
self.len.fetch_add(1, Ordering::SeqCst);
<span class="boring">}
</span></code></pre></pre>
<h3 id="出队算法-1"><a class="header" href="#出队算法-1">出队算法</a></h3>
<p>函数签名：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub fn pop(&amp;self) -&gt; Option&lt;T&gt;;
<span class="boring">}
</span></code></pre></pre>
<p>如前所述，出队算法本质上为两个阶段的操作。第一个阶段为尝试将 head 指针向后移动一位，同时在这里也要注意内存回收。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>let mut data = None;
if self.is_empty() {
    return data;
}

unsafe {
    let mut head: *mut Node&lt;T&gt;;
    loop {
        head = self.head.load(Ordering::Acquire);
        // 头结点的邻接节点
        let next = (*head).next.load(Ordering::Acquire);
        
        if next.is_null() {
            // 没有邻接节点，链表为空
            // 返回空
            return None;
        }
        
        if self.head
            .compare_exchange(head,next, Ordering::Release, Ordering::Relaxed)
            .is_ok()    // CAS 运算成功
        {
            data = (*next).item.take(); // 使用 take 获取 Option 中的数据
            break;  // 步进结束，跳出循环
        }
    }
    // 此时 self.head 的值为 next，head 应该被回收
    // 可以通过把内存所有权交给 Box 实现
    let _ = Box::from_raw(head);
    // Box 到达作用域尾部自动析构，释放 head
}
<span class="boring">}
</span></code></pre></pre>
<p>最后更新链表长度，返回出队的数据。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>self.len.fetch_sub(1, Ordering::SeqCst);
return data;
<span class="boring">}
</span></code></pre></pre>
<h3 id="析构"><a class="header" href="#析构">析构</a></h3>
<p>为了保证没有内存泄露，在析构时应释放整个链表。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>impl&lt;T&gt; Drop for LinkedQueue&lt;T&gt; {
    fn drop(&amp;mut self) {
        // 出队直到队列为空
        while self.pop().is_some() {}
        unsafe {
            // 释放头结点
            let _ = Box::from_raw(self.head);
        }
    }
}
<span class="boring">}
</span></code></pre></pre>
<h2 id="实现存在的问题"><a class="header" href="#实现存在的问题">实现存在的问题</a></h2>
<p>写了这么大块的 <code>unsafe</code>，也通过了编译。但是为了证明这个队列可用，还是应当编写测试用例证明算法实现正确。</p>
<h3 id="内存释放后写入"><a class="header" href="#内存释放后写入">内存释放后写入</a></h3>
<p>连续实现了简单插入、单生产者单消费者（并行）、多生产者单消费者（并行）和多生产者多消费者（并行）测试。前三个测试都顺利通过，说明链表可以保持有序性和一致性，使用 <code>miri</code> 进行简单检查也发现链表没有内存泄露问题。</p>
<p>但是在多生产者多消费者情形下，就会直接出现 segfault 退出测试程序，令人一头雾水。很显然本文的实现并不正确，可能在出队算法中出现了甚么问题。</p>
<p><code>Address Sanitizer</code>，简称 <code>ASan</code>，是一套可用于内存问题诊断的编译-链接技术。<code>Asan</code> 是用于排查运行时错误的利器，它的运行速度相比常用的 <code>Valgrind</code> 非常快，而且似乎不会严重影响程序的运行时行为——有时用 <code>valgrind</code> 跑程序并不一定会触发 Bug。</p>
<p>要在 rust 程序中使用 Asan，需要重新编译链接 rust 标准库，不过可以直接交给 cargo:</p>
<pre><code class="language-bash">export RUSTFLAGS=-Zsanitizer=address
export RUSTDOCFLAGS=-Zsanitizer=address
</code></pre>
<p>然后</p>
<pre><code class="language-bash">cargo -Zbuild-std --target &lt;环境对应的工具链，如 x86_64-unknown-linux-gnu&gt; &lt;test 或者 run 等&gt;
</code></pre>
<p>即可。</p>
<p>使用 Asan 诊断，可以发现出现了 UAF (Use After Free) 问题。其中一种表现为一个线程在</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub fn pop() -&gt; Option&lt;T&gt; {
    //...
    {
        data = (*next).item.take(); // &lt;&lt;&lt; write at
        break;
    }
    //...
}
<span class="boring">}
</span></code></pre></pre>
<p>中写入了早在另一个线程的</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub fn pop() -&gt; Option&lt;T&gt; {
    // ...
    let _ = Box::from_raw(head); // &lt;&lt;&lt; free
    // ...
}
<span class="boring">}
</span></code></pre></pre>
<p>操作中被释放的内存。这是因为前一个线程在 CAS 成功后挂起，而另一个线程在其后完成了 pop() 操作并释放了前一个线程欲读取的内存块。</p>
<p>同时如果一个生产者在循环查找链表尾期间被挂起，而在被重新唤醒时原先的链表尾部也已经被释放，那么也会导致 UAF 问题。</p>
<h3 id="aba-问题"><a class="header" href="#aba-问题">ABA 问题</a></h3>
<p>由于 CAS 操作的特性，如果一个线程在执行<code>CAS(ptr, A, C)</code>操作之前被挂起，其后的线程将 <code>ptr</code> 的值几经修改后又偶然地改成了<code>A</code>，那么就会导致这条本应失败的 CAS 操作被执行，损坏整个链表。
要解决 ABA 问题，可以通过：</p>
<ol>
<li>Double Word CAS</li>
<li>实现论文中提到的 SafeRead 协议</li>
<li>实现引用计数机制
<ul>
<li>只要 A 不释放，就不会有其他线程可以申请A，就无从将 ptr 改回来了</li>
</ul>
</li>
<li>使用垃圾回收机制
<ul>
<li>原理同上</li>
</ul>
</li>
</ol>
<p>由于在这里时间不够了，后两个方法都可以顺便解决内存安全问题。鄙人太菜了也懒得手动实现一个带引用计数的 <code>AtomicPtr</code>。于是选择走第三条路，使用 <a href="https://docs.rs/crossbeam/latest/crossbeam">crossbeam</a> 库。</p>
<h2 id="基于-crossbeam-的实现"><a class="header" href="#基于-crossbeam-的实现">基于 crossbeam 的实现</a></h2>
<p>crossbeam 是一个 rust 并行库，实现了多种并行数据结构和 epoch 垃圾收集器。只需要在当前线程中使用 <code>crossbeam::epoch::pin()</code> 获取一个 <code>crossbeam::epoch::Guard</code>，即可将本线程纳入垃圾收集器的管辖之中。据介绍 crossbeam 的垃圾收集器性能主要和线程数目有关。</p>
<p>crossbeam 提供了 <code>Atomic&lt;T&gt;</code>、<code>Owned&lt;T&gt;</code> 和 <code>Shared&lt;T&gt;</code> 指针类型。<code>Atomic&lt;T&gt;</code> 类似 AtomicPtr，支持多种原子操作，但是在其上的<code>load</code>操作获得的是一个 <code>Shared&lt;T&gt;</code>。
<code>Shared&lt;T&gt;</code> 类似一个 <code>Arc&lt;T&gt;</code>，可能指向被多个线程共享的数据；<code>Owned&lt;T&gt;</code> 类似一个 <code>Box&lt;T&gt;</code> 指针，在离开作用域时会自动析构。
<code>Shared&lt;T&gt;</code> 指针不会自行析构。需要手动调用 <code>Guard</code> 类型对象的 <code>defer_destroy(Shared&lt;T&gt;)</code>，将其交给垃圾收集器。</p>
<p>以上的 UAF 错误主要来自于出队算法实现中，提前进行了共享数据的释放。也难怪，一个线程要提前释放<strong>其他线程要读写</strong>的数据，这本身就是 rust 的所有权机制和生命周期概念本身要尽力避免的。如果把释放的活交给垃圾收集器，自然就好多了。</p>
<p>具体实现算法就不多赘述了。主要在原来的链表基础上将 AtomicPtr 全换成了 Atomic 指针，并修改了释放内存的代码。</p>
<h2 id="性能测试"><a class="header" href="#性能测试">性能测试</a></h2>
<p>最终作为基准的数据结构为 <code>Mutex&lt;LinkedList&lt;T&gt;&gt;</code> 实现的队列。</p>
<p>虽然手写的实现存在 UAF 问题，但是在单消费者的情形下还是可以正常工作的。于是也对其进行了性能测试。
性能测试主要测量在单生产者单消费者情形下整个队列的带宽，最终的测试结果如下：</p>
<p><img src="pict/v2-349c70eac6e0ccc00313c32d46f58709_1440w.webp" alt="" /></p>
<p>红色代表纯手写无 GC 实现，绿色代表基于 crossbeam 的实现，而蓝色则为基准数据结构的实现。可以看出，无锁数据结构的效率相比有锁数据结构，确实是<strong>质的飞跃</strong>。</p>
<h2 id="完全代码与推荐阅读"><a class="header" href="#完全代码与推荐阅读">完全代码与推荐阅读</a></h2>
<p>最终实现的代码存放在该 GitHub <a href="https://github.com/clslaid/l3queue.git">仓库</a>。</p>
<ol>
<li><a href="https://course.rs/too-many-lists/intro.html">手把手实现 rust 链表</a></li>
<li><a href="https://doc.rust-lang.org/nomicon/">rust-nomicon</a></li>
<li><a href="https://rustmagazine.github.io/rust_magazine_2022/Q1/contribute/atom.html">Rust原子类型和内存排序</a></li>
<li><a href="https://gcc.gnu.org/wiki/Atomic/GCCMM/AtomicSync">内存顺序-gcc wiki</a></li>
</ol>
<h2 id="参考"><a class="header" href="#参考">参考</a></h2>
<ol>
<li>^<a href="https://zhuanlan.zhihu.com/p/527500869#ref_1_0">a</a><a href="https://zhuanlan.zhihu.com/p/527500869#ref_1_1">b</a>J. D. Valois, ‘Implementing Lock-Free Queues’, <em>In Proceedings of the Seventh International Conference on Parallel and Distributed Computing Systems, Las Vegas</em>, NV, 1994. pp.64–69. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.8674&amp;rep=rep1&amp;type=pdf">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.8674&amp;rep=rep1&amp;type=pdf</a></li>
</ol>
<p>编辑于 2022-06-14 01:50</p>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="../../empty.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="../../05_无畏并发/进击的Rust多线程——混合自旋锁/进击的Rust多线程——混合自旋锁.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="../../empty.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="../../05_无畏并发/进击的Rust多线程——混合自旋锁/进击的Rust多线程——混合自旋锁.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="../../elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="../../clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
